This invention relates to a method and system for selecting the two smallest numbers from a set of multibit numbers more quickly than has heretofore been possible.
When searching for the minimum of two multibit binary numbers that are unsigned (so that the most significant bit of each number represents magnitude information rather than sign information), one can begin the comparison of the numbers at the most significant bit (MSB). If the MSB of a first number is a “1” and the MSB of a second number is a “0”, then the second number is smaller than the first number and therefore is the minimum as between those two numbers. If the two MSBs are the same (whether “0” or “1”), then evaluation of the next MSB is necessary and so on until a bit position is reached at which the bits are not the same.
Extending this to selecting a minimum of three or more unsigned multibit binary numbers, the numbers can be evaluated in pairs in tournament-ladder fashion, with the candidates narrowed by half at each stage. At each stage, a plurality of pairs is evaluated simultaneously, and the duration of each stage is the duration of the longest comparison in that stage, which in turn is the comparison that requires evaluation of the greatest number of bits until bits that are not identical are found—i.e., the longest comparison is for the pair in which the two numbers have the greatest number of identical MSBs.
For some applications, it is necessary to find not only the smallest number in a group of numbers, but also the second-smallest number—i.e., the problem presented is to find the two smallest numbers in a set of numbers. In the process described above, the second-smallest number may be the result of the comparison in one of the pairs from which the smallest number was not selected. Alternatively, it may be that the other number in the pair from which the smallest number was selected, while larger than the smallest number, is nevertheless smaller than any of the other comparison results and therefore is the second-smallest number. Thus to select the second-smallest number requires comparing the other number in the pair from which the smallest number was selected, and all of the results of the comparisons in the pairs from which the smallest number was not selected. Typically, this is done in a cascaded tree, and therefore the required comparison is between the other number in the pair from which the smallest number was selected, and the result of one other comparison. Even so, however, that comparison heretofore could not be made until the determination of the smallest number had been made.